package leetcode101.search_problem.dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code4
 * @Description 46. Permutations
 * Given an array nums of distinct integers, return all the possible permutations.
 * You can return the answer in any order.
 *
 *
 * Example 1:
 *
 * Input: nums = [1,2,3]
 * Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * Example 2:
 *
 * Input: nums = [0,1]
 * Output: [[0,1],[1,0]]
 * Example 3:
 *
 * Input: nums = [1]
 * Output: [[1]]
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-01 9:05
 */
public class Code4 {

    public static void main(String[] args) {
        int[] nums = new int[] {1, 2, 3};
        System.out.println(permute(nums).toString());
    }

    public static List<List<Integer>> res = new ArrayList<>();

    public static List<List<Integer>> permute(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    public static void dfs(int[] nums, int pos) {
        if (pos == nums.length - 1) {
            List<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            res.add(temp);
            return;
        }

        for (int i = pos; i < nums.length; i++) {
            swap(nums, pos, i);
            dfs(nums, pos + 1);
            swap(nums, pos, i);
        }
    }

    public static void swap(int[] nums, int pos1, int pos2) {
        int temp = nums[pos1];
        nums[pos1] = nums[pos2];
        nums[pos2] = temp;
    }

}
